package com.omybug.algorithm;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @author wuguojian
 * @description
 * @date 2022/10/13 下午3:32
 **/
public class ArrayTest {


    @Test
    public void t3() {
        int[] nums = {2,8,5,6,7,3,4,1,2};
        int k = 5;
        int result = q3(nums.length - k + 1, nums, 0, nums.length - 1);
        System.out.println(result);
    }

    /**
     * 寻找一数组中前K个最大的数
     */
    public int q3(int k, int[] nums, int start, int end) {
        int pivot = nums[end];
        int left = start;
        int right = end;

        while (true) {
            while (nums[left] < pivot && left < right) {
                left++;
            }
            while (nums[right] >= pivot && right > left) {
                right--;
            }
            if (left == right) {
                break;
            }
            q3swap(nums, left, right);
        }

        q3swap(nums, left, end);

        if (k == left + 1) {
            return pivot;
        } else if (k < left + 1) {
            return q3(k, nums, start, left - 1);
        } else {
            return q3(k, nums, left + 1, end);
        }
    }

    private void q3swap(int[] nums, int n1, int n2) {
        int tmp = nums[n1];
        nums[n1] = nums[n2];
        nums[n2] = tmp;
    }

    @Test
    public void t2() {
        int[] a = {1, 3, 5, 7, 9, 0, 10, 5};
        int target = 10;
        int[] result = q2(a, target);
        System.out.println(a[result[0]] + " " + a[result[1]]);
    }

    /**
     * 找出数组中和为S的一对组合，找出一组就行
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] q2(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int[] a = new int[2];
        map.put(nums[0], 0);
        for (int i = 1; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                a[0] = map.get(target - nums[i]);
                a[1] = i;
                return a;
            } else {
                map.put(nums[i], i);
            }
        }
        return a;
    }


    @Test
    public void t1() {
        int[] a = {1, 2, 3, 3, 1};
        System.out.println(q1(a));
    }

    /**
     * 一个数组，除一个元素外其它都是两两相等，求那个元素?
     * 异或运算：两个位相同为0，相异为1
     */
    public int q1(int[] a) {
        int len = a.length, res = 0;
        for (int i = 0; i < len; i++) {
            res = res ^ a[i];
        }
        return res;
    }


}
